#!/usr/bin/python
# -*- coding:utf-8 -*-
#希尔排序
#@author: wklken@yeah.net


def shell_sort(l):
    print l
    size = len(l)
    step = size/2
    #外层是步长
    while step >= 1:
        print step
        #里层是简单的插入排序  ，往前插入
        print "index ",range(size-1, step-1, -1)
        for i in range(size-1, step-1, -1):
            value = l[i]
            while i - step >= 0 and value < l[i-step]:
                l[i] = l[i-step]
                i -= step
            l[i] = value 
        step /= 2
        print l
    print l
        
l = [8, 4, 3, 7, 6, 5, 2, 1]
shell_sort(l)     
    